题目分析

小伙伴们遇到这样的题目，不能傻乎乎的去配对，要从中间找到规律，能否使用贪心的思路进行求解呢？

贪心

如何配对能使最大数对和最小呢？小伙伴想一想，如果将最大值和次大值配对，那么无论后面的元素如何配对，最大数对和都是最大值和次大值之和，这是最大数对和最大的情况。同理，如果想使最大数对和最小，能否将最大值和最小值配对呢？让次大值和次小值配对，让他们的值都尽量相等，是不是更合理一些？

这里不妨设最大值为max，最小值为min，以及任意两个值为m和n，组成$min \le n \le m \le max$
此时有三种配对方法
max + min和m + n，max + m和min + n，max + n和min + m
因为$max + m \ge max + min$且$max + n \ge max + min$，因此将最大值和最小值进行配对的方法是最优的。

推广到n个数对也是可以证明的，感兴趣的小伙伴们可以参考官方题解。因此本题可以排序，求将第i个元素和倒数第i个元素配对，然后计算最大值即可。

算法的时间复杂度为$O(nlog(n))$，空间复杂度为$O(1)$

下面是Java语言的题解

class Solution {
    public int minPairSum(int[] nums) {
        Arrays.sort(nums);
        int res = 0;
        for (int i = 0; i < nums.length / 2; i++) {
            res = Math.max(res, nums[i] + nums[nums.length - 1 - i]);
        }
        return res;
    }
}

刷题总结

本题是一个非常有趣的数学题，这里告诉大家的是在考试的过程中，有思路就可以去写，只要不限制次数，时间就是最重要的。不需要每一道题都严格证明，可以在考试完成后再进行推导。